package leetcode.editor.cn;

import java.util.Arrays;

public class Bag01 {
    public static void main(String[] args) {
        int[] weight = new int[]{1,3,4};
        int[] value = new int[]{15,20,30};
        int bagsize = 4;
        bagproblem(weight,value,bagsize);
    }
    //二维dp数组实现
    public static void bagproblem(int[] weight,int[] value,int bagsize){
        int n = weight.length;
        int[][] dp = new int[n+1][bagsize+1];

        for (int i = 1; i <= n ; i++) {//遍历物品
            for (int j = 1; j <= bagsize; j++) {//遍历容量
                if(j < weight[i-1]){//第i个物品的大小大于当前容量，第i个物品不能放入背包
                    dp[i][j] = dp[i-1][j];
                }else{//第i个物品能够放入背包
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i-1]] + value[i-1]);
                }
            }
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= bagsize ; j++) {
                System.out.printf("%5d",dp[i][j]);
            }
            System.out.println();
        }

    }
    //一维dp数组实现
    public static void bagproblem2(int[] weight,int[] value,int bagsize){
        int n = weight.length;
        int[] dp = new int[bagsize + 1];
        for (int i = 0; i < n; i++) {
            for (int j = bagsize; j >=weight[i] ; j--) {//倒序遍历
                dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]);
            }
            for (int num: dp) {
                System.out.print(num+" ");
            }
            System.out.println();
        }
    }
    //完全背包问题
    public static void bagcomplete(int[] weight,int[] value,int bagsize){
        int n = weight.length;
        int[] dp = new int[bagsize+1];
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <=bagsize ; j++) {//正序遍历
                dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
            }
            for (int num: dp) {
                System.out.print(num+" ");
            }
            System.out.println();
        }
    }
}
